// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-04 14:44
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class TriangleNumber {
    /**
     * 给定整形数组确认数组可以构成的三角形数
     */
    public int triangleNumber(int[] nums) {
        // 排序 + 二分查找
        int n = nums.length;
        int ans = 0;
        Arrays.sort(nums);
        // 找到最大满足要求值k，将值k - j累加到结果
        for (int i = 0; i < n; i++) {
            // 三角形最短边
            int a = nums[i];
            for (int j = i + 1; j < n - 1; j++) {
                // 三角形第二长边
                int b = nums[j];
                // 使用二分查找最大满足边
                ans += bSearch(nums, a, b, j);
            }
        }
        return ans;
    }

    /**
     * 使用二分查找获取指定数组中最大第三条边位置
     *
     * @param nums
     * @param a
     * @param b
     * @param j
     * @return
     */

    private int bSearch(int[] nums, int a, int b, int j) {
        int n = nums.length;
        int k = j;
        int left = j + 1;
        int right = n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] < (a + b)) {
                // 当前值还可以更大
                k = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return k - j;
    }


//    private int bSearch(int[] nums, int a, int b, int j) {
//        int n = nums.length;
//        for (int i = j + 1; i < n; i++) {
//            if (a + b <= nums[i]) {
//                return i - j - 1;
//            }
//        }
//        return n - j - 1;
//    }


    @Test
    public void shout() {
        int[] nums = {2, 2, 3, 4};
        System.out.println(triangleNumber(nums));
    }
}